40. 项目排期

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on('line', (line) => {
    if(!this.tasks) {
        this.tasks = lines.split(' ').map(Number);
    } else {
        const N = parseInt(line);
        console.log(canTimes(this.tasks, N));
    }
});

function canTimes(tasks, k) {
    tasks.sort((a,b)=>b-a);
    let l = tasks[0];
    let r = tasks.reduce((a,b)=>a+b, 0);
    while(l < r) {
        let mid = Math.floor((l+r)/2);
        if(canFinish(tasks, k, mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

function canFinish(task, k, limit) {
    let workers = new Array(k).fill(0);
    return backtrack(tasks, workers, 0, limit);
}

function backtrack(tasks, workers, index, limit) {
    if(index >= tasks.length) {
        return true;
    }
    let current = tasks[index];
    for(let i=0; i<workers.length; i++) {
        if(workers[i]+current<= limit) {
            workers[i] += current;
            if(backtrack(tasks, workers, index+1, limit)) {
                return true;
            }
            workers[i] -= current;
        }
        if(worker[i] === 0 || workers[i] + current === limit) {
            break;
        }
    }
    return false;
}